package org.liaohailong.helloworld.sort;

/**
 * Author: liaohailong
 * Time: 2021/8/2 16:30
 * Describe: 快速排序
 */
public class QuickSort implements ISort {

    @Override
    public void sort(int[] arr) {
        if (arr.length <= 1) return;
        _sort(arr, 0, arr.length - 1);
    }

    private void _sort(int[] arr, int i, int j) {
        if (i < j) {
            int m = partition(arr, i, j);
            _sort(arr, i, m - 1);
            _sort(arr, m + 1, j);
        }
    }

    private int partition(int[] arr, int i, int j) {
        int base = arr[i];
        while (i < j) {
            while (arr[j] > base && i < j) j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            while (arr[i] < base && i < j) i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = base;
        return i;
    }
}
